\begin{section}{Desarrollo}
	En este trabajo práctico aproximamos $\pi$ evaluando hasta un término dado la \texttt{Serie de Gregory}, la \texttt{Fórmula de Machin} y la \texttt{Serie de Ramanujan}.
	Como dichos métodos se implementan mediante aritmética finita de $t$ dígitos pretendemos analizar el comportamiento numérico de cada uno de estos métodos.
	 
	\begin{subsection}{Analisis teórico}
		A continuación analizamos la propagación del error de cada una de las series en el tercer término (en función de los errores de los primeros).\\
		
		Para simplificar dicha tarea calculamos previamente el error de operaciones comunes a las $tres$ series (division, suma, resta y multiplicación).\\
		
		Sea $\funcFull{div(x,y)} {\frac{x}{y}}$.\\
		
		$\e{div}{x,y,:}{\frac{\frac{x}{y}\ev{x}}{f} + \frac{\frac{-xy}{y^2}\ev{y}}{f} + \er{:}{x,y}} = 
		\frac{\frac{x}{y}\ev{x}}{\frac{x}{y}} + \frac{\frac{-x}{y}\ev{y}}{\frac{x}{y}} + \er{:}{x,y} = \ev{x} - \ev{y} + \er{:}{x,y}$\\
		
		Sea $\funcFull{sum(x,y)}{x+y}$\\
	
		$\e{sum}{x,y,+} = \frac{x}{x+y}\ev{x} + \frac{y}{x+y}\ev{y} + \er{+}{x,y}$\\
		
		Sea $\funcFull{resta(x,y)}{x-y}$\\
	
		$\e{resta}{x,y,-} = \frac{x}{x-y}\ev{x} - \frac{y}{x-y}\ev{y} + \er{-}{x,y}$\\
		
		Sea $\funcFull{mult(x,y)}{x*y}$\\
	
		$\e{mult}{x,y,*} = \frac{y*x}{x*y}\ev{x} + \frac{x*y}{x*y}\ev{y} + \er{*}{x,y} = \ev{x} + \ev{y} + \er{*}{x,y}$\\
		
		Sea $\funcFull{pot(x,y)}{x^y}$\\
		
		$\e{pot}{x,y,POT} = \frac{yx^{y-1}x}{x^y}\ev{x}+\frac{x^y ln(x) y}{x^y}\ev{y} + \er{POT}{x,y} = y\ev{x} + ln(x) y\ev{y} + \er{POT}{x,y}$\\
	
		\underline{Nota:} Realizamos la mayor cantidad de operaciones posibles en el tipo de datos $entero$ ya que de esta manera no poseen error, es decir, son exactas.
		Asumimos que el algoritmo nunca se va a ejecutar con una cantidad de iteraciones tal que desborde.\\
		
		\input{gregory.tex}
		\newpage
		\input{machin.tex}
		\newpage
		\input{ramanujan.tex}
		\newpage
		
	\end{subsection}
	\begin{subsection}{Implementación}
		Al necesitar manejar presición arbitraria los tipos de datos nativos del lenguaje C++ no satisfacían nuestras necesidades.
		
		Una solución encontrada a este problema, fue implementar un tipo de datos (clase $Real$) con esta funcionalidad (presición variable). La clase $Real$ implementa los operadores básicos: suma, resta, multiplicación. división y asignación, los observadores sobre la presición y truncamiento, y funciones para visualización de la información del $Real$ en stdout. Se exporta además dos métodos con funcionalidad importante, uno de ellos para convertir el $Real$ en $double$ (tipo nativo de C++) y otro método que dado un $double$ modifica la instancia $Real$, representando ahora, el valor pasado por parámetro.
		
		Como precondición de este trabajo práctico la precisión máxima de digitos (en base 2) del cálculo de $\pi$ debe ser a lo sumo 51 bits.
		Utilizamos el tipo $double$ de C++ como cimiento de nuestra clase $Real$. Las operaciones aritméticas sobre $Real$ consisten en convertirlos en $double$, realizar la operación correspondiente y transformar el resultado nuevamente en un $Real$, aplicándole previamente el algoritmo de truncamiento
		 %o redondeo según corresponda 
		acorde a los parámetros de entrada del programa (cantidad de dígitos).
		
		Fuera de la clase implementamos el cálculo de raíz cuadrada, arco tangente y exponenciación de $Real$. Se tomó esta decisión porque el uso de estas operaciones sólo tiene sentido en instancias de $Real$ en situaciones complejas (por ejemplo el cálculo de $\pi$). Tomamos como modelo la implementación de estas operaciones en C++ que requiere la inclusión de una biblioteca (cmath).
		
		La implementación de todos los algoritmos del cálculo de $\pi$ maximizan el uso de variables de tipo entero ya que las cuentas en número flotante poseen error mientras que enteros no. Cuando los cálculos dejan de tener sentido en el mundo de los enteros o su precisión no es suficiente, se crea una instancia de $Real$ que represente al valor entero y se continúa operando sobre este tipo. Una instancia de $Real$ se puede generar a partir de un entero de 64 bits con signo o de un $double$.\\
		   
	   A continuación detallamos las optimizaciones de los algoritmos:

		\begin{itemize}
			\item \underline{Gregory:} Refactorizamos nuestra implementación original de la serie que consistía en respetar el orden de los sumandos según el enunciado como las operaciones internas de cada uno de ellos. A continuación se detalla en lenguaje matemático los cambios realizados.\\
							
				$\sum_{n=0}^{\infty}\frac{(-1)^n}{2n+1} = \sum_{n \in \mathbb{N} / n\;mod(2)=0}^{\infty}\frac{1}{2n+1}-\sum_{n \in \mathbb{N} / n\;mod(2)=1}^{\infty}\frac{1}{2n+1}$\\
				
				Al hacerlo de esta manera en la ejecución de cada iteración del algoritmo evitamos el cálculo de una potencia o la utilización de una sentencia $if$ para determinar el signo, al costo de almacenar dos números que acumulan las sumas.
				
				Por otro lado, decidimos calcular $2n+1$ en un tipo de dato entero de 64 bits sin signo ya que de esta forma podemos evitar el error en el cálculo (a diferencia de si se realizara con números flotantes) y sería necesario un $n$ muy grande (cantidad de sumandos de la serie) para producir $overflow$.
				
			\item \underline{Machin:} Este algoritmo ejecuta la función $arctan$ la cual realiza la optimización antes mencionada.
			
			\item \underline{Ramanujan:} Este algoritmo fue rediseñado en varias oportunidades al observar diferentes problemas en cada implementación que realizamos. Entre sus operaciones encontramos la función factorial la cual en pocas iteraciones (en enteros sin signo de 64 bits) produce $overflow$. Sabiendo que el rango de valores representable en $double$, y por consiguiente en $Real$ es mayor al de cualquier entero de 64 bits, optamos por realizar la operación factorial en nuestro tipo de datos ($Real$).
			
		Nuestra primer aproximación fue definir la función factorial, la cual dado un $n$ calculaba la $\prod_{k=1}^{n}{k}$. Observamos que la cantidad de operaciones elementales que factorial realiza en cada llamada es lineal en función de $n$. El uso que se le da en el algoritmo de $Ramanujan$ es calcular el factorial de números consecutivos pudiéndose entonces, reutilizar el resultado de la iteración previa.\VSP
		
		A continuación se muestra un breve pseudcódigo del uso de la función factorial en el algoritmo de $Ramanujan$ (primera implementación).
		
		$\func{Ramanujan}{n}$\\
		\tab\FOR j=0 \TO n\\
		\tab\tab$factorial(4*j)$\\
		\tab\tab\tab.\\
		\tab\tab\tab.\\
		\tab\tab\tab.\\
		\tab\END
		
		\VSP
		
		Sabiendo que factorial es \Ode{n} y la cantidad de iteraciones del ciclo $for$ es $n$ y suponiendo que el resto de las operaciones del ciclo son constantes el algoritmo tiene complejidad cuadrática en función de $n$.\VSP

		A continuación se muestra un breve pseudocódigo del cálculo del factorial acumulando en una variable el resultado de la iteración anterior.\VSP
		
		$\func{Ramanujan}{n}$\\
		\tab $acum\_fact=1$\\
		\tab\FOR j=1 \TO n\\
		\tab\tab $i = 4*j$\\
		\tab\tab$acum\_fact = acum\_fact*(i-1)*(i-2)*(i-3)*i$\\
		\tab\tab\tab.\\
		\tab\tab\tab.\\
		\tab\tab\tab.\\
		\tab\END
		
		\VSP
		
		De esta forma, se realiza una cantidad constante de multiplicaciones en cada iteración del ciclo $for$ para el cálculo del factorial (suponiendo el resto de las operaciones del ciclo de costo constante) el algoritmo tiene complejidad lineal en función de $n$.
		
		La complejidad final del algoritmo de $Ramanujan$ no es esta ya que entre las operaciones del ciclo $for$ se encuentra la operación potencia con costo lineal en función del exponente ($4*j$). La complejidad es de \Ode{n^2}.
		
		\underline{Observación:} De manera similar a la implementación del factorial, se puede realizar el cálculo de la potencia utilizando acumuladores. Dado que esta función es utilizada en más de un algoritmo decidimos reutilizar código.
		
		Cabe mencionar que el primer término de la serie es un valor constante y entero, por lo que decidimos excluirlo del cálculo de la sumatoria y adicionarlo al final (por ese motivo la implementación final itera de 1 a n).
		\end{itemize}
		
		Para facilitar el desarrollo del programa se generaron varias funciones auxiliares de impresión de información. A la hora de hacer los test no era suficiente la visualización provista por la salida standard de C++. Estas visualizaciones como por ejemplo mostrar el $double$ bit a bit facilitaron la comprensión y analisis de errores programáticos.
		
	\end{subsection}
\end{section}
